{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "深度优先搜索结果:\n",
      "当前访问节点: 7\n",
      "节点 7 入栈\n",
      "当前访问节点: 4\n",
      "节点 4 入栈\n",
      "当前访问节点: 2\n",
      "节点 2 入栈\n",
      "当前访问节点: 6\n",
      "节点 6 入栈\n",
      "节点 6 出栈\n",
      "节点 2 出栈\n",
      "当前访问节点: 9\n",
      "节点 9 入栈\n",
      "节点 9 出栈\n",
      "节点 4 出栈\n",
      "当前访问节点: 3\n",
      "节点 3 入栈\n",
      "节点 3 出栈\n",
      "节点 7 出栈\n"
     ]
    }
   ],
   "source": [
    "def dfs(graph, start, visited=None, stack=None):\n",
    "    if visited is None:\n",
    "        visited = set()\n",
    "    if stack is None:\n",
    "        stack = []\n",
    "    \n",
    "    print(\"当前访问节点:\", start)\n",
    "    visited.add(start)\n",
    "    stack.append(start)\n",
    "    print(\"节点\", start, \"入栈\")\n",
    "    for neighbor in graph[start]:\n",
    "        if neighbor not in visited:\n",
    "            dfs(graph, neighbor, visited, stack)\n",
    "    \n",
    "    print(\"节点\", stack.pop(), \"出栈\")\n",
    "\n",
    "# 用邻接表表示图\n",
    "graph = {\n",
    "    7: [4, 3],\n",
    "    4: [2, 9],\n",
    "    3: [],\n",
    "    2: [6],\n",
    "    9: [],\n",
    "    6: []\n",
    "}\n",
    "\n",
    "# 从节点7开始深度优先搜索\n",
    "print(\"深度优先搜索结果:\")\n",
    "dfs(graph, 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "邻接矩阵：\n",
      "[[0 1 0 0 0 0 0 0]\n",
      " [1 0 1 0 0 0 0 0]\n",
      " [0 1 0 1 0 0 0 0]\n",
      " [0 0 1 0 1 0 0 0]\n",
      " [0 0 0 1 0 1 0 0]\n",
      " [0 0 0 0 1 0 1 0]\n",
      " [0 0 0 0 0 1 0 1]\n",
      " [0 0 0 0 0 0 1 0]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "# 给定的数组\n",
    "array = [2, 6, 8, 5, 3, 7, 1, 4]\n",
    "n = len(array)\n",
    "\n",
    "# 初始化邻接矩阵为全0\n",
    "adj_matrix = np.zeros((n, n), dtype=int)\n",
    "\n",
    "# 将数组中相邻元素的索引之间的连接关系表示为1\n",
    "for i in range(n - 1):\n",
    "    adj_matrix[i][i + 1] = 1\n",
    "    adj_matrix[i + 1][i] = 1\n",
    "\n",
    "print(\"邻接矩阵：\")\n",
    "print(adj_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "邻接矩阵：\n",
      "[0, 1, 1, 0, 0, 0, 0, 0]\n",
      "[1, 0, 0, 1, 1, 0, 0, 0]\n",
      "[1, 0, 0, 0, 0, 1, 1, 0]\n",
      "[0, 1, 0, 0, 0, 0, 0, 1]\n",
      "[0, 1, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 1, 0, 0, 0, 0, 0]\n",
      "[0, 0, 1, 0, 0, 0, 0, 0]\n",
      "[0, 0, 0, 1, 0, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "def build_adj_matrix(array):\n",
    "    n = len(array)\n",
    "    adj_matrix = [[0] * n for _ in range(n)]\n",
    "\n",
    "    for i in range(n):\n",
    "        left_child = 2 * i + 1\n",
    "        right_child = 2 * i + 2\n",
    "\n",
    "        if left_child < n:\n",
    "            adj_matrix[i][left_child] = 1\n",
    "            adj_matrix[left_child][i] = 1\n",
    "\n",
    "        if right_child < n:\n",
    "            adj_matrix[i][right_child] = 1\n",
    "            adj_matrix[right_child][i] = 1\n",
    "\n",
    "    return adj_matrix\n",
    "\n",
    "# 给定的数组\n",
    "array = [2, 6, 8, 5, 3, 7, 1, 4]\n",
    "\n",
    "# 构建邻接矩阵\n",
    "adj_matrix = build_adj_matrix(array)\n",
    "\n",
    "# 输出邻接矩阵\n",
    "print(\"邻接矩阵：\")\n",
    "for row in adj_matrix:\n",
    "    print(row)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2: [6, 8]\n",
      "6: [5, 3]\n",
      "8: [7, 1]\n",
      "5: [4]\n",
      "3: [ ]\n",
      "7: [ ]\n",
      "1: [ ]\n",
      "4: [ ]\n"
     ]
    }
   ],
   "source": [
    "def build_adjacency_list(arr):\n",
    "    adjacency_list = {}\n",
    "    \n",
    "    for i, node_value in enumerate(arr):\n",
    "        neighbors = []\n",
    "        \n",
    "        # 计算相邻节点的索引\n",
    "        left_index = i * 2 + 1\n",
    "        right_index = i * 2 + 2\n",
    "        \n",
    "        # 添加相邻节点到列表\n",
    "        if left_index < len(arr):\n",
    "            neighbors.append(arr[left_index])\n",
    "        if right_index < len(arr):\n",
    "            neighbors.append(arr[right_index])\n",
    "        \n",
    "        # 将节点值及其相邻节点列表添加到邻接表中\n",
    "        adjacency_list[node_value] = neighbors if neighbors else '[ ]'\n",
    "    \n",
    "    return adjacency_list\n",
    "\n",
    "# 数组\n",
    "arr = [2, 6, 8, 5, 3, 7, 1, 4]\n",
    "\n",
    "# 构建邻接表\n",
    "adj_list = build_adjacency_list(arr)\n",
    "\n",
    "# 打印邻接表\n",
    "for node_value, neighbors in adj_list.items():\n",
    "    print(f\"{node_value}: {neighbors}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs(层数,其他参数):\n",
    "    if (出局判断):  #到达最底层或满足退出条件\n",
    "        更新答案  #答案一般用全局变量表示\n",
    "        return  #返回到上一层\n",
    "    \n",
    "    剪枝  #在进一步dfs之前进行剪枝\n",
    "\n",
    "    for(枚举下一层可能的情况):  #对每一个情况继续dfs\n",
    "        if(used[i] == 0):  #如果状态i没有被占用，就可以进入下一层\n",
    "            used[i] == 1  #标记状态i，表示已经被用过，在更底层不能被使用\n",
    "            dfs(层数+1,其他参数)  #下一层\n",
    "            used[i] = 0  #恢复状态，回溯时，不影响上一层对这个状态的使用\n",
    "\n",
    "    return  #返回上一层"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 4 3 2 9 6 "
     ]
    }
   ],
   "source": [
    "def build_tree(nodes):\n",
    "    # 创建一个字典来表示树的结构\n",
    "    tree = {}\n",
    "    # 遍历每个节点，构建树的结构\n",
    "    for i, node in enumerate(nodes):\n",
    "        # 根节点没有父节点\n",
    "        if i == 0:\n",
    "            continue\n",
    "        # 获取当前节点的父节点索引\n",
    "        parent = (i - 1) // 2\n",
    "        # 将当前节点添加到父节点的子节点列表中\n",
    "        tree.setdefault(nodes[parent], []).append(node)\n",
    "    return tree\n",
    "\n",
    "def bfs_tree(tree):\n",
    "    # 使用队列来进行广度优先搜索\n",
    "    queue = [list(tree.keys())[0]]  # 根节点的索引为0\n",
    "    # 遍历队列，逐层打印树节点\n",
    "    while queue:\n",
    "        node = queue.pop(0)\n",
    "        print(node, end=' ')\n",
    "        # 将当前节点的子节点添加到队列中\n",
    "        children = tree.get(node, [])\n",
    "        queue.extend(children)\n",
    "\n",
    "# 给定的数组表示树的节点\n",
    "nodes = (7, 4, 3, 2, 9, 6)\n",
    "# 构建树的结构\n",
    "tree = build_tree(nodes)\n",
    "# 以根节点开始进行BFS遍历\n",
    "bfs_tree(tree)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BFS 运行时间: 0.001008 秒\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import time\n",
    "\n",
    "def bfs(array):\n",
    "    result = []\n",
    "    queue = [array[0]]  # 用列表模拟队列，并将根节点放入队列中\n",
    "    index = 1  # 当前遍历到的数组索引\n",
    "\n",
    "    while queue:\n",
    "        node = queue.pop(0)  # 出队\n",
    "        result.append(node)  # 将出队的节点添加到结果中\n",
    "\n",
    "        left_child_index = 2 * index  # 左孩子节点的索引\n",
    "        right_child_index = 2 * index + 1  # 右孩子节点的索引\n",
    "\n",
    "        if left_child_index <= len(array):  # 检查左孩子节点是否在数组范围内\n",
    "            queue.append(array[left_child_index - 1])  # 将左孩子节点入队\n",
    "\n",
    "        if right_child_index <= len(array):  # 检查右孩子节点是否在数组范围内\n",
    "            queue.append(array[right_child_index - 1])  # 将右孩子节点入队\n",
    "\n",
    "        index += 1  # 更新当前遍历到的数组索引\n",
    "\n",
    "    return result\n",
    "\n",
    "# 生成100个随机数并转化为数组\n",
    "random_numbers = [random.randint(0, 1000) for _ in range(999)]\n",
    "\n",
    "# 测量函数运行时间\n",
    "start_time = time.time()\n",
    "result = bfs(random_numbers)\n",
    "end_time = time.time()\n",
    "\n",
    "# 计算运行时间\n",
    "running_time = end_time - start_time\n",
    "print(\"BFS 运行时间: {:.6f} 秒\".format(running_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BFS 运行时间: 0.002000 秒\n",
      "BFS 遍历结果: [371, 419, 901, 112, 608, 45, 592, 373, 539, 801, 880, 210, 741, 604, 824, 307, 248, 272, 159, 968, 376, 281, 899, 812, 96, 700, 896, 553, 522, 539, 196, 888, 187, 273, 165, 727, 469, 224, 454, 217, 462, 611, 278, 972, 783, 88, 518, 350, 656, 891, 935, 496, 606, 894, 511, 400, 879, 822, 82, 845, 498, 650, 563, 79, 962, 517, 722, 520, 280, 750, 438, 549, 85, 686, 179, 805, 542, 461, 754, 473, 165, 334, 496, 28, 499, 610, 108, 30, 868, 883, 218, 30, 737, 943, 342, 790, 786, 913, 418, 182, 577, 445, 643, 660, 960, 887, 482, 871, 54, 115, 605, 842, 599, 555, 542, 96, 694, 542, 742, 29, 129, 899, 793, 930, 999, 480, 883, 367, 955, 934, 867, 649, 936, 59, 887, 5, 53, 238, 725, 800, 372, 504, 392, 181, 620, 223, 569, 86, 391, 775, 629, 541, 216, 474, 20, 162, 476, 642, 36, 376, 78, 648, 191, 764, 686, 995, 537, 902, 776, 755, 530, 418, 918, 470, 768, 446, 530, 992, 272, 642, 523, 381, 576, 8, 150, 116, 200, 170, 314, 12, 459, 254, 588, 94, 874, 433, 1000, 144, 224, 605, 509, 534, 977, 297, 49, 396, 272, 466, 476, 650, 960, 879, 910, 554, 568, 340, 309, 170, 128, 920, 777, 889, 751, 650, 224, 743, 644, 52, 712, 958, 443, 454, 87, 420, 32, 998, 71, 890, 6, 881, 226, 928, 411, 439, 763, 936, 210, 691, 193, 20, 563, 46, 974, 449, 974, 96, 673, 771, 299, 739, 326, 827, 40, 715, 365, 639, 333, 841, 570, 226, 777, 776, 818, 507, 125, 978, 899, 700, 532, 280, 316, 342, 713, 408, 373, 139, 518, 435, 475, 874, 647, 759, 243, 537, 44, 655, 687, 899, 935, 926, 209, 1, 458, 826, 918, 225, 703, 432, 20, 537, 951, 190, 95, 421, 854, 159, 54, 899, 23, 475, 194, 264, 672, 293, 176, 406, 160, 851, 537, 893, 275, 318, 799, 269, 255, 118, 404, 596, 633, 977, 790, 920, 539, 73, 489, 866, 78, 821, 628, 689, 720, 435, 71, 968, 992, 924, 839, 571, 616, 326, 896, 450, 911, 402, 403, 843, 286, 375, 636, 841, 150, 162, 38, 492, 452, 897, 342, 936, 932, 22, 53, 384, 910, 579, 97, 524, 880, 441, 59, 366, 689, 358, 642, 391, 334, 767, 862, 588, 992, 382, 458, 453, 935, 265, 382, 291, 355, 467, 420, 884, 791, 309, 706, 550, 590, 414, 462, 373, 352, 946, 61, 168, 269, 106, 693, 261, 504, 458, 537, 714, 749, 155, 816, 825, 582, 680, 421, 730, 936, 123, 878, 357, 9, 629, 857, 804, 637, 370, 461, 179, 759, 107, 760, 282, 344, 764, 399, 86, 921, 804, 523, 552, 786, 499, 795, 219, 129, 138, 483, 442, 284, 39, 666, 860, 725, 695, 775, 182, 258, 364, 247, 649, 249, 759, 602, 464, 280, 147, 656, 421, 889, 287, 891, 354, 63, 501, 231, 345, 542, 550, 587, 566, 611, 154, 319, 95, 558, 734, 262, 654, 55, 777, 757, 193, 900, 289, 818, 628, 287, 177, 408, 536, 108, 782, 880, 357, 912, 769, 33, 682, 948, 476, 563, 955, 312, 264, 832, 110, 48, 698, 340, 755, 920, 670, 174, 541, 491, 461, 942, 957, 842, 438, 930, 142, 944, 354, 519, 651, 846, 143, 376, 211, 334, 844, 309, 893, 116, 233, 573, 370, 184, 118, 44, 403, 749, 340, 853, 367, 757, 757, 916, 398, 440, 354, 630, 939, 127, 603, 819, 395, 169, 32, 697, 17, 218, 159, 214, 424, 51, 474, 129, 155, 717, 362, 275, 411, 423, 275, 225, 552, 300, 366, 876, 514, 61, 404, 973, 367, 863, 864, 753, 496, 112, 864, 834, 24, 42, 153, 1, 919, 325, 134, 519, 133, 994, 367, 455, 2, 230, 721, 694, 88, 387, 438, 518, 785, 972, 141, 828, 442, 906, 490, 166, 856, 10, 697, 207, 317, 99, 342, 432, 156, 8, 693, 525, 432, 89, 811, 170, 907, 328, 661, 337, 840, 294, 818, 503, 833, 856, 647, 533, 199, 862, 543, 680, 729, 925, 601, 178, 359, 20, 187, 771, 111, 815, 913, 975, 291, 362, 375, 240, 299, 581, 580, 79, 979, 821, 256, 971, 244, 378, 182, 499, 248, 558, 58, 838, 818, 534, 974, 18, 633, 767, 924, 859, 761, 892, 835, 202, 631, 473, 466, 925, 336, 522, 488, 23, 473, 714, 279, 875, 215, 48, 978, 600, 249, 484, 716, 328, 155, 215, 259, 563, 665, 230, 490, 361, 132, 78, 107, 76, 556, 163, 558, 815, 22, 449, 494, 694, 212, 808, 52, 341, 149, 104, 729, 433, 501, 213, 38, 555, 510, 890, 902, 424, 805, 418, 146, 614, 420, 405, 767, 420, 305, 545, 334, 176, 518, 18, 255, 295, 820, 575, 226, 189, 761, 726, 586, 264, 932, 730, 728, 505, 617, 860, 561, 428, 530, 951, 366, 893, 722, 39, 744, 554, 982, 776, 894, 309, 918, 301, 950, 828, 386, 100, 644, 876, 874, 287, 523, 557, 267, 372, 408, 816, 890, 374, 745, 152, 739, 121, 578, 689, 256, 565, 657, 131, 202, 510, 941, 61, 925, 602, 891, 142, 764, 412, 451, 95, 413, 946, 289, 829, 507, 981, 319, 538, 396, 739, 249, 953, 955, 127, 706, 464, 422, 180, 826, 30, 859, 984, 451, 449, 193, 988, 55, 617, 663, 752, 326, 579, 798, 427, 653, 674, 554, 613, 458, 754, 564, 921, 409, 109, 728, 295, 892, 282, 62, 899, 757, 639, 389, 162, 641, 693, 900, 791, 789, 501, 494, 806, 576, 119, 297, 628, 291, 692, 3, 967, 972, 119, 469, 921, 61, 682, 334, 447, 935, 693, 552, 615, 774, 420, 338, 845, 543, 48, 13, 112, 724, 233, 971, 548, 778, 606, 113, 47, 567, 703, 758, 178, 450, 800, 558, 503, 126, 411, 830, 340, 677, 70, 141, 470, 491, 807, 972, 399, 530, 609, 807, 300, 684, 277, 688, 728, 864, 337, 670, 694]\n"
     ]
    }
   ],
   "source": [
    "import queue\n",
    "import time\n",
    "import random\n",
    "\n",
    "def bfs(array):\n",
    "    result = []\n",
    "    q = queue.Queue()\n",
    "    q.put(array[0])  # 将根节点放入队列中\n",
    "    index = 1  # 当前遍历到的数组索引\n",
    "\n",
    "    while not q.empty():\n",
    "        node = q.get()  # 出队\n",
    "        result.append(node)  # 将出队的节点添加到结果中\n",
    "\n",
    "        left_child_index = 2 * index  # 左孩子节点的索引\n",
    "        right_child_index = 2 * index + 1  # 右孩子节点的索引\n",
    "\n",
    "        if left_child_index <= len(array):  # 检查左孩子节点是否在数组范围内\n",
    "            q.put(array[left_child_index - 1])  # 将左孩子节点入队\n",
    "\n",
    "        if right_child_index <= len(array):  # 检查右孩子节点是否在数组范围内\n",
    "            q.put(array[right_child_index - 1])  # 将右孩子节点入队\n",
    "\n",
    "        index += 1  # 更新当前遍历到的数组索引\n",
    "\n",
    "    return result\n",
    "\n",
    "# 生成100个随机数并转化为数组\n",
    "random_numbers = [random.randint(0, 1000) for _ in range(999)]\n",
    "\n",
    "# 测量函数运行时间\n",
    "start_time = time.time()\n",
    "result = bfs(random_numbers)\n",
    "end_time = time.time()\n",
    "\n",
    "# 计算运行时间\n",
    "running_time = end_time - start_time\n",
    "print(\"BFS 运行时间: {:.6f} 秒\".format(running_time))\n",
    "print(\"BFS 遍历结果:\", result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BFS 运行时间: 0.000000 秒\n",
      "BFS 遍历结果: [316, 658, 508, 600, 862, 507, 586, 192, 75, 58, 318, 848, 901, 184, 83, 299, 526, 66, 783, 944, 260, 82, 322, 429, 960, 808, 141, 940, 479, 33, 824, 266, 736, 863, 830, 155, 719, 538, 981, 811, 400, 330, 285, 894, 192, 551, 922, 48, 352, 424, 402, 227, 388, 770, 873, 238, 714, 415, 651, 595, 818, 196, 141, 585, 202, 189, 382, 103, 792, 581, 362, 699, 623, 511, 948, 93, 973, 179, 78, 259, 321, 637, 140, 875, 671, 409, 146, 523, 993, 729, 454, 277, 315, 487, 876, 82, 850, 86, 587, 828, 767, 936, 756, 433, 306, 364, 90, 507, 673, 21, 17, 352, 515, 446, 133, 92, 575, 957, 88, 468, 687, 85, 607, 419, 295, 627, 353, 237, 599, 653, 134, 832, 912, 828, 205, 962, 443, 777, 960, 870, 946, 662, 605, 150, 131, 960, 269, 306, 767, 390, 466, 239, 336, 518, 674, 162, 424, 386, 845, 841, 867, 220, 490, 368, 874, 409, 414, 470, 846, 204, 141, 789, 551, 999, 739, 78, 837, 622, 124, 602, 187, 180, 435, 33, 831, 518, 400, 43, 487, 834, 422, 202, 298, 198, 24, 733, 575, 487, 586, 749, 361, 140, 120, 705, 447, 683, 2, 247, 919, 798, 410, 11, 316, 854, 73, 353, 2, 986, 596, 440, 813, 54, 730, 591, 930, 304, 881, 780, 666, 282, 79, 819, 503, 695, 177, 933, 219, 575, 540, 338, 257, 387, 81, 533, 692, 517, 814, 638, 548, 291, 521, 365, 219, 612, 1000, 290, 735, 941, 95, 142, 663, 192, 117, 995, 993, 876, 67, 938, 84, 186, 28, 57, 335, 51, 511, 857, 223, 312, 119, 731, 555, 978, 329, 924, 345, 229, 617, 343, 186, 362, 640, 375, 160, 333, 20, 26, 889, 81, 300, 794, 519, 310, 542, 18, 328, 942, 212, 469, 810, 607, 31, 111, 131, 273, 957, 935, 192, 916, 760, 819, 512, 1000, 564, 415, 294, 498, 243, 263, 385, 647, 237, 851, 970, 654, 991, 338, 505, 132, 643, 667, 953, 425, 497, 11, 522, 952, 91, 434, 443, 904, 215, 596, 344, 903, 792, 106, 901, 492, 278, 319, 850, 74, 61, 573, 230, 158, 145, 950, 355, 844, 543, 105, 132, 997, 10, 789, 445, 422, 176, 975, 184, 82, 444, 243, 325, 609, 256, 399, 408, 915, 369, 890, 148, 345, 762, 642, 784, 770, 378, 128, 355, 644, 561, 822, 374, 64, 690, 172, 432, 14, 148, 741, 529, 525, 185, 269, 645, 654, 665, 887, 454, 252, 804, 509, 841, 870, 881, 364, 58, 305, 414, 862, 347, 764, 506, 391, 906, 957, 399, 918, 88, 160, 243, 58, 344, 42, 211, 328, 683, 888, 536, 139, 47, 691, 464, 140, 545, 178, 654, 278, 314, 148, 438, 475, 989, 838, 375, 256, 521, 408, 644, 132, 966, 443, 513, 956, 92, 89, 287, 411, 151, 307, 180, 615, 782, 287, 573, 362, 853, 684, 396, 272, 912, 627, 798, 801, 988, 449, 975, 908, 153, 496, 890, 490, 89, 612, 583, 438, 318, 839, 38, 565, 608, 35, 807, 520, 475, 725, 26, 622, 25, 169, 47, 573, 384, 540, 266, 167, 46, 346, 189, 828, 48, 132, 242, 327, 653, 709, 934, 250, 479, 876, 776, 67, 821, 205, 222, 76, 450, 734, 171, 760, 806, 692, 138, 191, 347, 200, 858, 121, 638, 41, 551, 414, 834, 735, 306, 736, 783, 811, 780, 338, 102, 585, 943, 307, 848, 216, 165, 98, 941, 74, 822, 664, 653, 659, 976, 724, 51, 679, 774, 161, 906, 374, 209, 99, 887, 10, 443, 711, 425, 325, 31, 97, 665, 318, 898, 238, 449, 586, 472, 899, 936, 762, 146, 579, 688, 977, 129, 967, 876, 964, 619, 17, 73, 221, 231, 852, 946, 213, 450, 399, 193, 24, 155, 348, 405, 431, 820, 676, 947, 811, 400, 478, 184, 248, 713, 797, 497, 210, 498, 458, 310, 366, 469, 239, 122, 968, 124, 839, 330, 296, 912, 400, 777, 71, 328, 912, 337, 558, 479, 748, 845, 921, 569, 966, 292, 540, 331, 370, 626, 659, 95, 241, 207, 725, 322, 823, 915, 952, 517, 128, 789, 34, 154, 394, 73, 723, 22, 193, 846, 920, 626, 247, 968, 584, 434, 986, 700, 883, 538, 432, 940, 373, 605, 982, 611, 74, 357, 749, 413, 185, 473, 416, 59, 230, 248, 317, 984, 979, 137, 592, 580, 687, 261, 616, 515, 806, 719, 607, 111, 593, 984, 272, 431, 765, 671, 26, 689, 172, 1000, 796, 497, 671, 540, 183, 273, 768, 916, 472, 663, 894, 708, 792, 602, 162, 392, 676, 290, 877, 62, 975, 635, 837, 125, 672, 567, 212, 600, 59, 173, 476, 362, 58, 256, 745, 860, 697, 894, 541, 312, 213, 859, 404, 879, 950, 251, 43, 293, 877, 853, 191, 392, 586, 105, 956, 976, 723, 705, 999, 437, 344, 127, 73, 456, 837, 331, 598, 403, 289, 962, 873, 195, 371, 736, 25, 697, 219, 508, 371, 695, 247, 741, 863, 643, 778, 843, 851, 858, 237, 722, 543, 557, 347, 816, 872, 630, 482, 836, 587, 506, 675, 523, 467, 750, 577, 503, 995, 352, 712, 981, 177, 822, 756, 533, 127, 272, 716, 435, 80, 954, 173, 917, 789, 578, 40, 436, 288, 40, 732, 879, 740, 911, 850, 650, 507, 527, 131, 238, 44, 912, 675, 815, 441, 702, 635, 898, 751, 34, 703, 129, 743, 145, 260, 317, 578, 387, 31, 358, 81, 693, 711, 554, 111, 146, 601, 217, 935, 700, 719, 725, 310, 968, 58, 763, 278, 563, 464, 765, 861, 119, 850, 425, 528, 905, 152, 861, 450, 326, 256, 426, 455, 502, 89, 621, 35, 535, 109, 66, 170, 890, 353, 386, 647, 657, 351, 183, 527, 845, 735, 970, 275, 694, 245, 402, 854, 591, 686, 446, 937, 87, 456, 217, 433, 307, 773, 927, 174, 830, 93, 190, 853, 925, 314, 353, 176, 863, 857, 33, 198, 8, 6, 223, 71, 802, 520, 72, 952, 179]\n"
     ]
    }
   ],
   "source": [
    "import collections\n",
    "import time\n",
    "import random\n",
    "\n",
    "def bfs(array):\n",
    "    result = []\n",
    "    q = collections.deque()\n",
    "    q.append(array[0])  # 将根节点放入队列中\n",
    "    index = 1  # 当前遍历到的数组索引\n",
    "\n",
    "    while q:\n",
    "        node = q.popleft()  # 出队\n",
    "        result.append(node)  # 将出队的节点添加到结果中\n",
    "\n",
    "        left_child_index = 2 * index  # 左孩子节点的索引\n",
    "        right_child_index = 2 * index + 1  # 右孩子节点的索引\n",
    "\n",
    "        if left_child_index <= len(array):  # 检查左孩子节点是否在数组范围内\n",
    "            q.append(array[left_child_index - 1])  # 将左孩子节点入队\n",
    "\n",
    "        if right_child_index <= len(array):  # 检查右孩子节点是否在数组范围内\n",
    "            q.append(array[right_child_index - 1])  # 将右孩子节点入队\n",
    "\n",
    "        index += 1  # 更新当前遍历到的数组索引\n",
    "\n",
    "    return result\n",
    "\n",
    "# 生成100个随机数并转化为数组\n",
    "random_numbers = [random.randint(0, 1000) for _ in range(999)]\n",
    "\n",
    "# 测量函数运行时间\n",
    "start_time = time.time()\n",
    "result = bfs(random_numbers)\n",
    "end_time = time.time()\n",
    "\n",
    "# 计算运行时间\n",
    "running_time = end_time - start_time\n",
    "print(\"BFS 运行时间: {:.6f} 秒\".format(running_time))\n",
    "print(\"BFS 遍历结果:\", result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "当前路径: ['A', 'B']\n",
      "当前路径: ['A', 'C']\n",
      "当前路径: ['A', 'B', 'D']\n",
      "当前路径: ['A', 'B', 'E']\n",
      "当前路径: ['A', 'C', 'F']\n",
      "当前路径: ['A', 'B', 'E', 'F']\n",
      "所有路径： [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]\n"
     ]
    }
   ],
   "source": [
    "def bfs_with_all_paths(graph, start, end):\n",
    "    queue = [(start, [start])]  # 初始时将起点及其路径放入队列中\n",
    "    all_paths = []  # 用于存储所有找到的路径\n",
    "\n",
    "    while queue:\n",
    "        node, path = queue.pop(0)  # 出队\n",
    "        if node == end:\n",
    "            all_paths.append(path)  # 找到目标节点，将路径添加到结果列表中\n",
    "        for neighbor in graph[node]:\n",
    "            if neighbor not in path:  # 避免回路\n",
    "                new_path = path + [neighbor]  # 生成新路径\n",
    "                queue.append((neighbor, new_path))  # 将邻居节点及其路径加入队列\n",
    "                # 输出搜索过程中的路径\n",
    "                print(\"当前路径:\", new_path)\n",
    "    \n",
    "    return all_paths\n",
    "\n",
    "# 示例图结构\n",
    "graph = {\n",
    "    'A': ['B', 'C'],\n",
    "    'B': ['D', 'E'],\n",
    "    'C': ['F'],\n",
    "    'D': [],\n",
    "    'E': ['F'],\n",
    "    'F': []\n",
    "}\n",
    "\n",
    "start_node = 'A'\n",
    "end_node = 'F'\n",
    "\n",
    "all_paths = bfs_with_all_paths(graph, start_node, end_node)\n",
    "print(\"所有路径：\", all_paths)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "当前路径: ['A', 'B']\n",
      "当前路径: ['A', 'C']\n",
      "当前路径: ['A', 'B', 'D']\n",
      "当前路径: ['A', 'B', 'E']\n",
      "当前路径: ['A', 'C', 'F']\n",
      "当前路径: ['A', 'B', 'E', 'F']\n",
      "回溯路径： ['A', 'C', 'F']\n"
     ]
    }
   ],
   "source": [
    "def bfs_with_backtracking(graph, start, end):\n",
    "    queue = [(start, [start])]  # 初始时将起点及其路径放入队列中\n",
    "\n",
    "    while queue:\n",
    "        node, path = queue.pop(0)  # 出队\n",
    "        if node == end:\n",
    "            return path  # 找到目标节点，直接返回路径\n",
    "        for neighbor in graph[node]:\n",
    "            if neighbor not in path:  # 避免回路\n",
    "                new_path = path + [neighbor]  # 生成新路径\n",
    "                queue.append((neighbor, new_path))  # 将邻居节点及其路径加入队列\n",
    "                # 输出搜索过程中的路径\n",
    "                print(\"当前路径:\", new_path)\n",
    "\n",
    "    return None  # 如果没找到路径，则返回 None\n",
    "\n",
    "# 示例图结构\n",
    "graph = {\n",
    "    'A': ['B', 'C'],\n",
    "    'B': ['D', 'E'],\n",
    "    'C': ['F'],\n",
    "    'D': [],\n",
    "    'E': ['F'],\n",
    "    'F': []\n",
    "}\n",
    "\n",
    "start_node = 'A'\n",
    "end_node = 'F'\n",
    "\n",
    "path = bfs_with_backtracking(graph, start_node, end_node)\n",
    "print(\"回溯路径：\", path)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "当前位置: (0, 0) 步数: 0\n",
      "当前位置: (0, 1) 步数: 1\n",
      "当前位置: (1, 1) 步数: 2\n",
      "当前位置: (1, 2) 步数: 3\n",
      "当前位置: (1, 3) 步数: 4\n",
      "当前位置: (2, 3) 步数: 5\n",
      "当前位置: (3, 3) 步数: 6\n",
      "当前位置: (2, 4) 步数: 6\n",
      "当前位置: (3, 2) 步数: 7\n",
      "当前位置: (2, 5) 步数: 7\n",
      "当前位置: (3, 1) 步数: 8\n",
      "当前位置: (1, 5) 步数: 8\n",
      "当前位置: (3, 5) 步数: 8\n",
      "当前位置: (1, 6) 步数: 9\n",
      "当前位置: (3, 6) 步数: 9\n",
      "当前位置: (1, 7) 步数: 10\n",
      "当前位置: (3, 7) 步数: 10\n",
      "当前位置: (4, 7) 步数: 11\n",
      "当前位置: (4, 8) 步数: 12\n",
      "当前位置: (4, 9) 步数: 13\n",
      "找到出口，步数: 13\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "def bfs(maze, start, end):\n",
    "    # 定义方向：上、下、左、右\n",
    "    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "    rows, cols = len(maze), len(maze[0])\n",
    "    \n",
    "    # 记录访问过的位置\n",
    "    visited = set()\n",
    "    visited.add(start)\n",
    "    \n",
    "    # 使用队列来进行广度优先搜索\n",
    "    queue = deque([(start, 0)])  # 元素为当前位置和步数\n",
    "    \n",
    "    while queue:\n",
    "        (x, y), steps = queue.popleft()\n",
    "        print(\"当前位置:\", (x, y), \"步数:\", steps)\n",
    "        \n",
    "        if (x, y) == end:\n",
    "            print(\"找到出口，步数:\", steps)\n",
    "            return\n",
    "        \n",
    "        # 探索当前位置的相邻位置\n",
    "        for dx, dy in directions:\n",
    "            nx, ny = x + dx, y + dy\n",
    "            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == '0' and (nx, ny) not in visited:\n",
    "                visited.add((nx, ny))\n",
    "                queue.append(((nx, ny), steps + 1))\n",
    "    \n",
    "    print(\"搜索结束，没有找到出口。\")\n",
    "\n",
    "maze = [\n",
    "    \"0011111111\",\n",
    "    \"1000100011\",\n",
    "    \"1110001111\",\n",
    "    \"1000100011\",\n",
    "    \"1111111000\"\n",
    "]\n",
    "\n",
    "start = (0, 0)  # 起点坐标\n",
    "end = (4, 9)    # 终点坐标\n",
    "\n",
    "bfs(maze, start, end)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
